package leetcode.dp;

import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;

/**
 * leetCode 698
 * Partition to K Equal Sum Subsets
 * 划分为k个相等的子集
 * 思路：动态规划
 * 一个动态规划问题。老规矩，定义一个一维的dp数组，其中dp[i]表示数字i是否是原数组的任意个子集合之和。
 对于遍历到的每个数字nums[i]，我们需要更新我们的dp数组，要更新[nums[i], target]之间的值，那么对于这个区间中的任意一个数字j，如果dp[j - nums[i]]为true的话，那么dp[j]就一定为true，于是地推公式如下：dp[j] = dp[j] || dp[j - nums[i]]         (nums[i] <= j <= target)。

 */
public class Dp698 {

    public static void main(String []args){
        Scanner sc = new Scanner(System.in);
        //利用hasNextXXX()判断是否还有下一输入项
        while (sc.hasNext()) {
            //利用nextXXX()方法输出内容
            String str = sc.next();
            List<Integer> input = Arrays.stream(str.split(",")).map(i -> { return Integer.parseInt(i); }).collect(Collectors.toList());
            System.out.println(Arrays.toString(input.toArray()));
            Integer [] nums = input.toArray(new Integer[input.size()]);
            new Dp698().canPartitionKSubsets(nums, 1);
        }
    }
    public boolean canPartitionKSubsets(Integer[] nums, int k) {
        int sum = 0;
        for(int i = 0 ; i< nums.length;i++) sum += nums[i];
        if(sum%k != 0 || sum <= 0) return false;
        // dp[i]表示sum/k为i时能否被分割
        boolean [] dp = new boolean[sum/k + 1];
        // 第一位就为sum/2时一定能分
        for(int i = 0;i <= sum/k ;i ++){
            dp[i] = (nums[0] == i);
        }
        for(int i = 1;i < nums.length ; i ++){
            for(int j = sum/k;j >= nums[i] ; j --){
                dp[j] = dp[j] || dp[j - nums[i]];
            }
        }
        return dp[sum/k];
    }
}
